๐งท ํธ๋ฆฌ
๊ฐ์ ๊ฐ์ง ๋ ธ๋(Node)์ ์ด ๋ ธ๋๋ค์ ์ด์ด์ฃผ๋ ๊ฐ์ (Edge)๋ก ์ด๋ฃจ์ด์ง ์๋ฃ๊ตฌ์กฐ์ด๋ค.
ํธ๋ฆฌ๋ผ๋ ์ด๋ฆ์ด ๋์จ ์ด์ ?
: ์ค์ ๋๋ฌด๋ฅผ ๊ฑฐ๊พธ๋ก ์ธ์๋์ ๋ฏํ ๋ชจ์์ ๋ณด์ด๊ธฐ ๋๋ฌธ์ด๋ค.
- ๊ทธ๋ฆผ์์, ๋ฐ์ดํฐ 1์ ๊ฐ์ง ๋ ธ๋๊ฐ ๋ฃจํธ ๋ ธ๋์ด๋ค.
- ๋ชจ๋ ๋ ธ๋๋ค์ 0๊ฐ ์ด์์ ์์ ๋ ธ๋๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฉฐ, "๋ถ๋ชจ-์์ ๊ด๊ณ"๋ก ๋ถ๋ฆฐ๋ค.
์ ํ ์๋ฃ๊ตฌ์กฐ์์ ๋ฐฐ์ด์ด๋ ๋ฆฌ์คํธ ๋ฑ๋ ์กด์ฌํ์ง๋ง, ํธ๋ฆฌ๊ฐ ๋์จ ์ด์ ๋ ๋ญ๊น?
-
์ผ๋ฐ ๋ฐฐ์ด์์ ์ฝ์ ์ด๋ ์ญ์ ๋ฅผ ํ๋๋ฐ ์ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค.
- ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ ์์์ ์ฝ์ ํ๋ ๊ฒฝ์ฐ ๋๋จธ์ง ๋ชจ๋ ์์๋ค์ ํ ์นธ์ฉ ๋ค๋ก ๋ฏธ๋ค์ผ ํ๋ฏ๋ก ์ต์ ์ ๊ฒฝ์ฐ, ์ ์๊ฐ ๋ณต์ก๋๊ฐ ๋์จ๋ค.
- ํ์ง๋ง ํธ๋ฆฌ๋ ํธํฅ ํธ๋ฆฌ๊ฐ ์๋ ์ด์, ์ ๋์ ์๊ฐ์ผ๋ก ์ค์ฌ์ง๋ค.
๐ช ํน์ง
- Stack์ด๋ Queue์ ๊ฐ์ ์ ํ ๊ตฌ์กฐ๊ฐ ์๋ ๋น์ ํ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
- ๊ณ์ธต์ ๊ด๊ณ๋ฅผ ํํํ๋ค.
- ๋ฃจํธ ๋ ธ๋๋ฅผ ์ ์ธํ ๋ชจ๋ ๋ ธ๋๋ ๋จ ํ๋์ ๋ถ๋ชจ ๋ ธ๋๋ง์ ๊ฐ๋๋ค.
- ํธ๋ฆฌ์๋ ์ฌ์ดํด์ด ์กด์ฌํ ์ ์๋ค. (๋ง์ฝ ์ฌ์ดํด์ด ๋ง๋ค์ด์ง๋ค๋ฉด, ๊ทธ๋ํ์ด๋ค.)
- ๋ชจ๋ ๋ ธ๋๋ ์๋ฃํ์ผ๋ก ํํ์ด ๊ฐ๋ฅํ๋ค.
- ๋ฃจํธ์์ ํ ๋ ธ๋๋ก ๊ฐ๋ ๊ฒฝ๋ก๋ ์ ์ผํ ๊ฒฝ๋ก๋ฟ์ด๋ค.
- ๋ ธ๋์ ๊ฐ์๊ฐ N๊ฐ๋ฉด, ๊ฐ์ ์ N-1๊ฐ๋ฅผ ๊ฐ์ง๋ค.
๐ช ํธ๋ฆฌ ์ํ ๋ฐฉ์
ํธ๋ฆฌ์ ๋ฃจํธ๋ฅผ ๊ธฐ์ค์ผ๋ก ์ด 4๊ฐ์ง์ ์ํ ๋ฐฉ์์ด ์๋ค. ํธ๋ฆฌ๋ ์ ๊ทธ๋ฆผ์ ์ฌ์ฉํ๋ค.
-
์ ์ ์ํ(pre-order)
- ๊ฐ ๋ฃจํธ๋ฅผ ์์ฐจ์ ์ผ๋ก ๋จผ์ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค. (Root -> ์ผ์ชฝ ์์ -> ์ค๋ฅธ์ชฝ ์์)
1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 13 -> 7 -> 14
-
์ค์ ์ํ(in-order)
- ์ผ์ชฝ ํ์ ํธ๋ฆฌ๋ฅผ ๋ฐฉ๋ฌธํ ํ ๋ฃจํธ๋ฅผ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค. (์ผ์ชฝ ์์ -> Root -> ์ค๋ฅธ์ชฝ ์์)
8 -> 4 -> 9 -> 2 -> 10 -> 5 -> 11 -> 1 -> 6 -> 13 -> 3 -> 14 -> 7
-
ํ์ ์ํ(post-order)
- ์ผ์ชฝ ํ์ ํธ๋ฆฌ๋ถํฐ ํ์๋ฅผ ๋ชจ๋ ๋ฐฉ๋ฌธํ ํ ๋ฃจํธ๋ฅผ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค. (์ผ์ชฝ ์์ -> ์ค๋ฅธ์ชฝ ์์ -> Root)
8 -> 9 -> 4 -> 10 -> 11 -> 5 -> 2 -> 13 -> 6 -> 14 -> 7 -> 3 -> 1
-
๋ ๋ฒจ ์ํ(level-order)
- ๋ฃจํธ๋ถํฐ ๊ณ์ธต๋ณ๋ก ๋ฐฉ๋ฌธํ๋ ๋ฐฉ์์ด๋ค.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14
๐ช ๊ตฌํ
ํธ๋ฆฌ์ ๊ตฌํ์ ์ํด์๋ ์๋์ ์ ๋ณด๋ค์ด ํ์ํ๋ค.
- ๋ฐ์ดํฐ์ ์ฐ๊ฒฐ ์ํ๋ฅผ ์ ์ฅํ ํด๋์ค ๊ณต๊ฐ(=๋ ธ๋) ์์ฑ
- ๊ฐ๊ฐ์ ๋ ธ๋๋ค์ ๊ฐ ์ ์ฅ
- ๋ ธ๋ ๊ฐ ์ฐ๊ฒฐ ์ํ ์ ์
class Node {
Node left;
Node right;
String value;
public Node(String value) {
this.left = null;
this.right = null;
this.value = value;
}
}
- ๊ฐ ๋ ธ๋๋ค์ ๊ฐ๊ณผ, ์ผ์ชฝ, ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋๋ฅผ ๊ฐ์ง๋ค.
class Tree {
Node root;
int size = 0;
}
- ํธ๋ฆฌ๋ ๋ฃจํธ ๋ ธ๋์, ๊ทธ ํฌ๊ธฐ ์ ๋ณด๋ฅผ ๊ฐ์ง๋ค.